Computational Complexity and Program Structure

Loop programs have the property that an upper bound on the running time of a program is determined by its structure. Each program consists only of assignment and iteration (loop) statements, but all of the arithmetic functions commonly encountered in digital computation can be computed by Loop programs. A simple procedure for bounding the running time is shown to be best possible; some programs actually achieve the bound, and it is effectively undecidable whether a program runs faster than the bound. The complexity of functions can be measured by the loop structure of programs which compute them. The functions computable by Loop programs are precisely the primitive recursive functions.